/*
 * Copyright (C) 2008-2009 Spark Zheng
 *
 * segment_tree.h
 * 
 * a segment-tree implementation use rbtree
 * to storage the ip-segment black-write list
 * for yaez_iprbl server
 *
 */

#ifndef IPRBL_SGTREE_H_
#define IPRBL_SGTREE_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <dlib/global.h>
#include <netinet/in.h>

typedef struct sg_head S_SGTREE_HEAD;
typedef struct sg_node S_SGTREE_NODE;

/*
 * SG_WALKER_FN, travel function when in/post/preorder sgtree. 
 */
typedef void (*SG_WALKER_FN)(S_SGTREE_NODE *node, void *arg);

typedef enum {
	SG_RED = 0,
	SG_BLACK
} SG_COLOR_T;

typedef enum {
	SG_EXACT = 1,	/* find the exact key */
	SG_OBSCURE	/* if exact key not exist, return the follow */
} SG_STRATEGY_T;

struct sg_node {
	S_SGTREE_NODE	*left;
	S_SGTREE_NODE	*right;
	S_SGTREE_NODE	*parent;
	SG_COLOR_T	color;

	in_addr_t	ip_low;	    /* primer key */
	in_addr_t	ip_high;    /* auxiliary key */
};

struct sg_head {
	S_SGTREE_NODE	*sg_root;
	uint32_t	sg_count;
};

/* global node sg_leaf for stored only once */
extern S_SGTREE_NODE sg_leaf;

#define INIT_SG_HEAD(head) \
	({(head)->sg_root =&sg_leaf; \
	  (head)->sg_count = 0;})

#define INIT_SG_NODE(node, p, c) \
	({(node)->left = &sg_leaf; \
	  (node)->right = &sg_leaf; \
	  (node)->parent = p; \
	  (node)->color = c;})

#define SG_ROOT(head)		((head)->sg_root)
#define SG_COUNT(head)		((head)->sg_count)

#define SG_EMPTY(head)		(SG_ROOT(head) == &sg_leaf)

#define SG_LEFT(node)		((node)->left)
#define SG_RIGHT(node)		((node)->right)
#define SG_PARENT(node)		((node)->parent)
#define SG_COLOR(node)		((node)->color)

#define SG_IS_RED(node)		(!SG_COLOR(node))
#define SG_IS_BLACK(node)	(SG_COLOR(node))

#define SG_SET(node, left, right, parent, color)	do { \
	SG_PARENT(node) = parent; \
	SG_LEFT(node) = left; \
	SG_RIGHT(node) = right; \
	SG_COLOR(node) = color; } while (0)

#define SG_SET_RED(node)	(SG_COLOR(node) = SG_RED)
#define SG_SET_BLACK(node)	(SG_COLOR(node) = SG_BLACK)
#define SG_SET_LEFT(node, left)		(SG_LEFT(node) = left)
#define SG_SET_RIGHT(node, right)	(SG_RIGHT(node) = right)
#define SG_SET_PARENT(node, parent)	(SG_PARENT(node) = parent)

/* segment-tree apis, init for a tree with a head, exit for destroy a tree.
 * minimum, maximum, predecessor, successor, insert, delete, find, travel
 */

/* sg_init.
 * init a segment tree.
 * @head: tree-head.
 */
extern S_SGTREE_HEAD *sg_init(void);
/* sg_exit.
 * destroy a segment tree.
 * @head: tree-head.
 */
extern void sg_exit(S_SGTREE_HEAD *head);

/* sg_minimum.
 * find the minimum key node of a sub-tree.
 * @node: from which node
 */
extern S_SGTREE_NODE *sg_minimum(S_SGTREE_NODE *node);
/* sg_maximum.
 * find the maximum key node of a sub-tree.
 * @node: from which node
 */
extern S_SGTREE_NODE *sg_maximum(S_SGTREE_NODE *node);
/* sg_predecessor.
 * find the predecessor key node of a sub-tree.
 * @node: from which node
 */
extern S_SGTREE_NODE *sg_predecessor(S_SGTREE_NODE *node);
/* sg_successor.
 * find the successor key node of a sub-tree.
 * @node: from which node
 */
extern S_SGTREE_NODE *sg_successor(S_SGTREE_NODE *node);
/* sg_insert.
 * insert a node into segment-tree.
 * @head: segment tree head
 * @ip_low: the lower ip
 * @ip_high: the higher ip
 */
extern int sg_insert(S_SGTREE_HEAD *head, in_addr_t ip_low,
		     in_addr_t ip_high);
/* sg_delete.
 * delete a node from segment-tree.
 * @head: segment-tree head
 * @ip_low: the lower ip
 * @ip_high: the higher ip
 */
extern int sg_delete(S_SGTREE_HEAD *head, in_addr_t ip_low,
		     in_addr_t ip_high);
/* sg_find.
 * find a node from sg-tree by a key.
 * @head: sg-tree head
 * @ip_low: the lower ip
 * @ip_high: the higher ip
 */
extern S_SGTREE_NODE *sg_find(S_SGTREE_HEAD *head, in_addr_t ip_low,
			      in_addr_t ip_high);
/* sg_inorder.
 * inorder traver a sg-tree.
 * @head: sg-tree head
 * @walker: walker function
 * @arg: find cmd (seems to be a little complex)
 */
extern int sg_inorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg);
/* sg_postorder.
 * postorder traver a sg-tree.
 * @head: sg-tree head
 * @walker: walker function
 * @arg: find cmd (seems to be a little complex)
 */
extern int sg_postorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg);
/* sg_preorder.
 * preorder traver a sg-tree.
 * @head: sg-tree head
 * @walker: walker function
 * @arg: find cmd (seems to be a little complex)
 */
extern int sg_preorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg);

#ifdef __cplusplus
}
#endif
#endif
